package com.zwj.interview.数组.差分数组;

/**
 * @Author: Zwj
 * @Date: 2022/9/15 15:12
 *
 * 差分数组是与前缀和数组所对应的一种逆操作，类似于求导和积分，也就是说，对差分数组求前缀和，
 * 可以得到原数组，同样的，对前缀和数组求差分，也可以得到原数组。
 */
// 差分数组工具类
public class Difference {
    // 差分数组
    private int[] diff;

    /* 输入一个初始数组，区间操作将在这个数组上进行 */
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /**
     *  给闭区间 [i, j] 增加 val（可以是负数）:
     *  当我们希望对原数组的某一个区间[l,r]施加一个增量inc时，
     *  差分数组d对应的变化是：d[l]增加inc，d[r+1]减少inc，并且这种操作是可以叠加的。
     *
     */
    public void increment(int i, int j, int val) {
        diff[i] += val;
        //注意这里：当 j+1 >= diff.length 时，说明是对 nums[i] 及以后的整个数组都进行修改，那么就不需要再给 diff 数组减 val 了
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    /* 返回结果数组 */
    public int[] result() {
        int[] res = new int[diff.length];
        // 根据差分数组构造结果数组
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }

}